package twoPointers;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//https://leetcode.cn/problems/3sum/description/
public class l_15 {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        //从左往右枚举第一个数nums[i], nums[i]右边的区间用双指针求两数之和为(0-nums[i]), 注意去重即可(为方便可用set), 因要求三数之和为0, 所以当nums[i] > 0时可直接退出循环
        for(int i = 0; (i < n - 2) && (nums[i] <= 0); i++) {
            if(i > 0 && nums[i] == nums[i - 1]) continue; //去重
            int left = i + 1, right = n - 1, target = -nums[i];
            while(left < right) {
                if(left > i + 1 && nums[left] == nums[left - 1]) ++left; //去重
                else if(right < n - 1 && nums[right] == nums[right + 1]) --right; //去重
                else {
                    int sum = nums[left] + nums[right];
                    if(sum == target) {
                        ans.add(List.of(nums[i], nums[left], nums[right]));
                        ++left;
                        --right;
                    } else if(sum > target) --right;
                    else ++left;
                }
            }
        }
        return ans;
    }
}
